package com.suxin.algorithm.graph;

import lombok.AllArgsConstructor;

import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @author Tang
 * @classname BFS
 * @description [ 广度优先 ]
 * @date 2023/1/10 16:10
 */
public class BFS {

    @AllArgsConstructor
    static class Points{
        private final Integer x;
        private final Integer y;
    }

    /**
     * 地图
     */
    private static final int[][] MAPS = new int[][]{
            {0,0,1,0},
            {0,0,0,0},
            {0,0,1,0},
            {0,1,0,0},
            {0,0,0,0}
    };

    /**
     * 标记数组
     */
    private static final boolean[][] MARK = new boolean[5][4];

    /**
     * 标记队列
     */
    private final Queue<Points> queue = new ArrayBlockingQueue<>(100);

    /**
     * 上下左右
     */
    private static final int[][] POSITION = new int[][]{
            {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    /**
     * 思路：探测式访问，访问过得位置加入到队列,在用新的位置进行探测
     * @param x x
     * @param y y
     */
    public void bfs(int x,int y,Points targetPoints) {
        queue.add(new Points(x, y));
        MARK[x][y] = true;
        int m = MARK[0].length;
        int n = MARK.length;
        while (!queue.isEmpty()) {
            Points points = queue.poll();
            for (int[] ints : POSITION) {
                int newX = points.x + ints[0];
                int newY = points.y + ints[1];
                // 越界检查 & 访问过的不需要在入队了
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && !MARK[newX][newY]) {
                    // 障碍物
                    if (MAPS[newX][newY] == 1) {
                        continue;
                    }
                    // 目标对比
                    if (newX == targetPoints.x && newY == targetPoints.y) {
                        System.out.println("true");
                        return;
                    }
                    MARK[newX][newY] = true;
                    // 新坐标入队
                    queue.add(new Points(newX, newY));
                }
            }
        }
        System.out.println("false");
    }

    public static void main(String[] args) {
        BFS bfs = new BFS();
        bfs.bfs(0, 0,new Points(3,2));
    }

}
